package SOS;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String[] a;
		int[] b = null;

		while (true) {
			String choice = sc.next();

			switch (choice) {
			case "fib":
				int n = sc.nextInt();
				for (int x = 1; x < n; x++) {
					System.out.print(fib(x) + " ");
				}
				System.out.println(fib(n));
				break;
			case "sort":
				sc.nextLine();
				String x = sc.nextLine();
				a = x.split(" ");
				b = covertToIntDigits(a);
				Arrays.sort(b);
				System.out.println(Arrays.toString(b));

				break;
			case "search":
				sc.nextLine();
				Arrays.sort(b);
				int c = sc.nextInt();
				int pos = Arrays.binarySearch(b, c);
				if (pos < 0)
					System.out.println(-1);
				else
					System.out.println(pos);
				break;
			case "getBirthDate":
				sc.nextLine();
				int x1 = sc.nextInt();
				for (int i = 0; i < x1; i++) {
					String id = sc.next();
					StringBuilder birthdate = new StringBuilder(id.substring(6, 14));
					String BD = new String(birthdate);
					BD = birthdate.substring(0,4)+'-'+birthdate.substring(4,6)+'-'+birthdate.substring(6,8);
					System.out.println(BD);
				}
				break;
			default:
				System.out.println("exit");
				break;
			}
		}

	}


	private static int[] covertToIntDigits(String[] strDigits) {
		int[] array = new int[strDigits.length];
		for (int i = 0; i < strDigits.length; i++) {
			array[i] = Integer.parseInt(strDigits[i]);
		}
		return array;
	}

	private static int fib(int n) {

		if (n == 1 || n == 2)
			return 1;
		else
			return fib(n - 1) + fib(n - 2);
	}
}
